// https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/
// Created by ade on 2022/9/13.
// 给定整数 k ，返回 组成满足上述条件的付费群体所需的《最小金额> 。精确到小数点后5位
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
        int len = quality.size();
        vector <vector<int>> p = {};
        for (int i = 0; i < len; i++) {
            p.push_back({quality[i], wage[i]});
        }
        auto cmp = [](vector<int> a, vector<int> b) {
            return double(a[0]) / double(a[1]) >= double(b[0]) / double(b[1]);
        };
        priority_queue < int, vector < vector < int >>, decltype(cmp) > q(cmp);
        for (auto &i : p) {
            q.push(i);
        }
        vector <vector<int>> res = {};
        while (!q.empty()) {
            res.push_back(q.top());
            cout << "quality:" << q.top()[0] << "--wage:" << q.top()[1] << endl;
            q.pop();
        }
        double sum = 10000.0;
        for (int i = 0; i < len - k; i++) {
            double topQ = double(res[i][0]);
            double topW = double(res[i][1]);

            cout << "q:" << topQ << ",w:" << topW << endl;
            double tmp = 0.0;
//            cout << topW << endl;
            for (int j = i; j < i + k; j++) {
                tmp += double(res[j][0]) / double(res[j][1]) * topW / topQ;
                cout << ",tmp:" << tmp;
            }
            cout << "tmp::" << tmp << endl;
            sum = min(sum, tmp);
        }
        return sum;
//
//
//        double topW = q.top()[1];
//        double topQ = q.top()[0];
//        cout << topW << "--" << topQ << endl;
//        while (!q.empty()) {
//            sum += topW / topQ * double(q.top()[0]);
//            q.pop();
//            k--;
//        }
//        return sum;
    }
};

int main() {
    Solution so;
    vector<int> q = {3, 1, 10, 10, 1};
    vector<int> w = {4, 8, 2, 2, 7};
    cout << so.mincostToHireWorkers(q, w, 3);
    return 0;
}